package leetcode101.ch4;

import java.util.Arrays;

//LC 34 在排序数组中查找元素的第一个和最后一个位置 给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
public class SearchRange {
    public int[] searchRange(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return new int[]{-1, -1};
        }
        int left = leftIdx(nums, target);
        int right = rightIdx(nums, target) - 1;
        System.out.println("l:"+ left + " r:"+right);
        if(left <= right && right < nums.length && nums[left] == target && nums[right] == target) {
            return new int[]{left, right};
        }
        return new int[]{-1, -1};

    }

    private int leftIdx(int[] nums, int target) {
        int l = 0, r = nums.length;
        int mid;
        while (l < r) {
            mid = (l + r) / 2;
            if (nums[mid] >= target) {
                r = mid;
            }else {
                l = mid + 1;
            }
        }
        return l;
    }

    private int rightIdx(int[] nums, int target) {
        int l = 0, r = nums.length;
        int mid;
        while (l < r) {
            mid = (l + r) / 2;
            if (nums[mid] > target) {
                r = mid;
            }else {
                l = mid + 1;
            }
        }
        return l;
    }

    public static void main(String[] args) {
        int[] nums = new int[]{5,7,7,8,8,10};
        int target = 8;
//        int[] nums = new int[]{1};
//        int target = 1;
        int[] res = new SearchRange().searchRange(nums, target);
        System.out.println(Arrays.toString(res));
    }
}
